package william.quicksort;

import java.util.concurrent.ThreadLocalRandom;

/**
 * @author ZhangShenao
 * @date 2024/1/29
 * @description <a href="https://leetcode.cn/problems/sort-an-array/">...</a>
 */
public class Leetcode912_排序数组 {
    /**
     * 采用快速排序实现
     */
    public int[] sortArray(int[] nums) {
        //边界条件校验
        if (nums == null || nums.length < 2) {
            return nums;
        }

        //递归调用
        quickSortRecursion(nums, 0, nums.length - 1);

        //返回排好序的数组
        return nums;
    }

    /**
     * 递归处理
     * nums[L,R]范围进行快速排序
     */
    private void quickSortRecursion(int[] nums, int L, int R) {
        //递归终止条件
        if (L >= R) {
            return;
        }

        //进行partition操作,找到等于区的范围
        int[] equalsArea = partition(nums, L, R);

        //递归调用,对小于区和等于区分别进行快速排序
        quickSortRecursion(nums, L, equalsArea[0] - 1);
        quickSortRecursion(nums, equalsArea[1] + 1, R);
    }

    /**
     * partition过程
     * 选定基准值,将整个数组划分成小于基准值、等于基准值和大于基准值三个区域
     * 最终返回一个包含2个元素的数组,分别记录等于区域的起始索引和终止索引
     */
    private int[] partition(int[] nums, int L, int R) {
        //随机选择一个元素,与R位置的元素进行交换,以此作为基准值
        int idx = ThreadLocalRandom.current().nextInt(L, R + 1);
        swap(nums, idx, R);
        int pivot = nums[R];

        //维护两个区域:小于区[L,less]和大于区[more,R]
        int less = L - 1;
        int more = R;

        //遍历数组,将每个元素与基准值进行比较
        int i = L;
        while (i < more) {
            int n = nums[i];
            if (n == pivot) {    //该元素=基准值,无需任何处理,直接跳到下一个元素
                i++;
            } else if (n < pivot) { //该元素<基准值,将该元素与小于区的下一个元素进行交换,同时将小于区向右移动,并跳到下一个元素
                swap(nums, ++less, i++);
            } else {    //该元素>基准值,将该元素与大于区的前一个元素进行交换,同时大于区向左移动,不跳下一个元素
                swap(nums, --more, i);
            }
        }

        //将R位置的元素与大于区的第一个元素进行交换
        swap(nums, more, R);

        //返回等于区的范围
        return new int[]{less + 1, more};
    }

    /**
     * 将数组nums中i和j索引的元素进行交换
     */
    private void swap(int[] nums, int i, int j) {
        int tmp = nums[i];
        nums[i] = nums[j];
        nums[j] = tmp;
    }
}
